package demo.practice.dp;

public class P264 {

    public static void main(String[] args) {
        P264 p264 = new P264();
        p264.nthUglyNumber(1548);
    }

    public void nthUglyNumber(int n) {

        int[] dp = new int[n];
        dp[0] = 1;

        for (int i = 1; i < n; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {

                if (dp[j] * 2 > dp[i - 1]) {
                        dp[i] = Math.min(dp[i], dp[j] * 2);
                }
                if (dp[j] * 3 > dp[i - 1]) {
                    dp[i] = Math.min(dp[i], dp[j] * 3);
                }
                if (dp[j] * 5 > dp[i - 1]) {
                    dp[i] = Math.min(dp[i], dp[j] * 5);
                }

            }
        }

        int[] dp2 = new int[n + 1];
        dp2[1] = 1;
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= n; i++) {
            int num2 = dp2[p2] * 2, num3 = dp2[p3] * 3, num5 = dp2[p5] * 5;
            dp2[i] = Math.min(Math.min(num2, num3), num5);
            if (dp2[i] == num2) {
                p2++;
            }
            if (dp2[i] == num3) {
                p3++;
            }
            if (dp2[i] == num5) {
                p5++;
            }
        }


        for (int i = 0; i < dp.length; i++) {
            if (dp[i] != dp2[i + 1]) {
                System.out.println(i);
            }
        }
        //return dp[n];


        //return dp[n-1];


    }
}
